package codingforgreat.lchot150;

public class Lc005 {
    //5.1
    int max = 0;
    int l = 0;
    int r = 0;
    public String longestPalindrome(String s) {
        char[] str = s.toCharArray();
        String res = null;
        for(int i = 0;i < str.length;i++){
            func(str,i,i);
            func(str,i,i + 1);
        }
        return s.substring(l,r);
    }
    public void func(char[] s,int i,int j){
        while(i >= 0 && j < s.length && s[i] == s[j]){
            if(j - i + 1 > max){
                max = j - i + 1;
                l = i;
                r = j + 1;
            }
            i--;
            j++;
        }
    }
    //5.2manacher

    public String longestPalindrome1(String s) {
        if(s == null || s.length() == 0){
            return "";
        }
        char[] str = makeMa(s);
        int R = -1;
        int C = -1;
        int[] parr = new int[str.length];//半径数组
        int max = Integer.MIN_VALUE;;
        int maxC = -1;
        for(int i = 0;i < str.length;i++){
            parr[i] = R > i ? Math.min(parr[2 * C - i],R - i):1;
            while(i + parr[i] < str.length && i - parr[i] >= 0){
                if(str[i + parr[i]] == str[i - parr[i]]){
                    parr[i]++;
                }else{
                    break;
                }
            }
            if(i + parr[i] > R){
                C = i;
                R = i + parr[i];
            }
            if(max < parr[i]){
                maxC = i;
                max = parr[i];
            }
        }
        return s.substring( (maxC - parr[maxC] + 1) / 2,((maxC - parr[maxC] + 1) / 2) + parr[maxC] - 1);
    }
    public char[] makeMa(String s){
        char[] s1 = s.toCharArray();
        char[] res = new char[2 * s.length() + 1];
        int index = 0;
        for (int i = 0; i < res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : s1[index++];
        }
        return res;
    }
}
